#include<vector>
#include<unordered_map>
using namespace std;

class LFUCache {
private:
    struct Node {
        int key_, val_, freq_;
        Node(int key,int val,int freq):key_(key),val_(val),freq_(freq){}
    };
    int capacity;
    int size;
    int minFreq;
    unordered_map<int, list<Node>::iterator> keyMap;
    unordered_map<int, list<Node>> freqMap;

    void update(int key) {
        auto iter = keyMap[key];
        auto& list = freqMap[iter->freq_];
        Node node(iter->key_, iter->val_, iter->freq_);
        list.erase(iter);
        if (list.empty()) {
            if (minFreq == node.freq_) ++minFreq;
            freqMap.erase(node.freq_);
        }
        node.freq_++;
        freqMap[node.freq_].push_front(node);
        keyMap[key] = freqMap[node.freq_].begin();
    }

public:
    LFUCache(int capacity):capacity(capacity),size(0),minFreq(0) {

    }

    int get(int key) {
        int val = -1;
        if (keyMap.find(key) != keyMap.end()) {
            val = keyMap[key]->val_;
            update(key);
        }
        return val;
    }

    void put(int key, int value) {
        if (capacity == 0) return;
        if (keyMap.find(key) != keyMap.end()) {
            keyMap[key]->val_ = value;
            update(key);
            return;
        }
        if (size >= capacity) {
            Node& node = freqMap[minFreq].back();
            keyMap.erase(node.key_);
            freqMap[minFreq].pop_back();
            if (freqMap[minFreq].empty()) {
                freqMap.erase(minFreq);
                ++minFreq;
            }
            --size;
        }
        ++size;
        Node node(key, value, 1);
        freqMap[1].push_front(node);
        keyMap[key] = freqMap[1].begin();
        minFreq = 1;
    }
};


int main() {
    LFUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(2);
    cache.get(2);
    cache.get(2);
    cache.put(3, 3);
}
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */